class Solution {
    public String longestPalindrome(String s) {
        char[] ss = s.toCharArray();
        int n = s.length();
        boolean[][] dp = new boolean[n][n];//是不是回文串

        int start = 0;
        int len = 0;

        for (int i = n - 1; i >= 0; i--) {
            //定j：从i开始向后
            for (int j = i; j < n; j++) {
                //前提是i和j元素一致
                if (ss[i] == ss[j]) {
                    if (i == j) {
                        dp[i][j] = true;
                    } else if (i + 1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                //更新
                if (dp[i][j] && j - i + 1 > len) {
                    len = j - i + 1;
                    start = i;
                }
            }
        }

        return s.substring(start, start + len);
    }
}